/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 九转苍翎
 * Date: 2025/8/21
 * Time: 22:42
 */
public class Solution {
    public int mySqrt(int x) {
        if (x < 1) {
            return 0;
        }
        long left = 1, right = x,mid = 1;
        //寻找左边界
        while(left < right){
            if (mid * mid <= x) {
                left = mid;
            }else {
                right = mid - 1;
            }
            mid = left + (right - left + 1) / 2;
        }
        return (int)left;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int ret = solution.mySqrt(2147395599);
        System.out.println(ret);
    }
}